bzoj 3994 [SDOI2015]约数个数和

题目链接

bzoj 3994: [SDOI2015]约数个数和

题解

结论与结论的证明参考了rqy的博客
计算$d(ij)$时，把ij的每个约数d映射到$(a=gcd(d,i),b=(gcd(d,i),\frac{d}{gcd(d, i)})$
可知$a,b$分别是$i,j$的因数，且$(a,b)$对应一个因数当且仅当$gcd(\frac ia, b) = 1$，所以

$$d(ij) = \sum_{x|i}\sum_{y|j} [gcd(\frac ix, y) = 1] = \sum_{x'|i}\sum_{y|j} [gcd(x', y) = 1]$$

有了这个式子之后

$$\sum_{i=1}^n\sum_{j=1}^m d(ij)$$ $$=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j} [gcd(x, y) = 1]$$ $$=\sum_{i=1}^n\sum_{j=1}^m \left\lfloor\frac ni\right\rfloor \left\lfloor\frac mj\right\rfloor [gcd(i, j) = 1]$$ $$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i}\sum_{d|j}\mu(d)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor$$ $$=\sum_{d=1}^{min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\mu(d)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor$$ $$=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{i}\rfloor\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{j}\rfloor$$

用$f(x)=\sum_{i=1}^{x}\lfloor\frac{x}{i}\rfloor$表示1-x的约数个数和

$\sum_{d=1}^{min(n,m)}\mu(d)f(\lfloor\frac{n}{d}\rfloor)f(\lfloor\frac{m}{d}\rfloor)$预处理$\mu(n)$前缀和
对于$f$我们可以$O(n\sqrt n)$预处理,查询为$O(\sqrt n)$

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn = 50007;
#define int long long
inline int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='0')f=-1;c=getchar();}
    while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
    return x*f;
}
int f[maxn],mu[maxn],num,prime[maxn];
bool vis[maxn];
inline int countf(int x) {
    int ans=0;
    for(int i=1,last;i<=x;i=last+1) {
        last=x/(x/i);
        ans+=x/i*(last-i+1);
    }
    return ans;
}
void get_mu() {
    mu[1]=1;
    for(int i=2;i<maxn;++i) {
        if(!vis[i])prime[++num]=i,mu[i]=-1;
        for(int j=1;j<=num&&i*prime[j]<maxn;++j) {
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)mu[prime[j]*i]=0;
            else mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<maxn;++i)mu[i]+=mu[i-1];
}
void init() {
    for(int i=1;i<maxn;++i)f[i]=countf(i);
    get_mu();
}
int solve(int n,int m) {
    int ans=0;
    for(int i=1,last;i<=std::min(n,m);i=last+1) {
        last=std::min(n/(n/i),m/(m/i));
        ans+=(mu[last]-mu[i-1])*f[n/i]*f[m/i];
    }
    return ans;
}
main() {
    init();
    int T=read();
    for(;T--;) {
        printf("%lld\n",solve(read(),read()));
    }
    int tmp=0;
    return 0;
}